package newcoder;

import org.junit.Test;

/**
 * @Classname _42
 * @Description TODO
 * @Date 2021/7/22 22:21
 * @Created by Alberthch
 *
 * 题目描述：输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。
 * 解答：滑动窗口思想，使用双指针进行滑动就行,使得每一个元素为起始位置的可能性都要进行尝试
 * 注意：由提示得到数组元素数量至少为1
 */
public class newcoder_42_MaxSum {
    // 方法1：暴力法，两层for循环，时间复杂度为O(n^2),不符合题目要求
    public static int maxSubArray(int[] nums) {

        int max = Integer.MIN_VALUE;
        int add = 0;
        for (int i = 0; i < nums.length; i++) {
            add = 0 ;
            for (int j = i; j < nums.length; j++) {
                add += nums[j];
                max = Math.max(add,max);

            }

        }
        return max;
    }

    // 方法2：动态规划
    public int maxSubArrayLeecode1(int[] nums) {
        int pre = 0, maxAns = nums[0];
        for (int x : nums) {
            pre = Math.max(pre + x, x);
            maxAns = Math.max(maxAns, pre);
        }
        return maxAns;
    }

    // 方法3：前缀和思想
    public int maxSubArrayLeecode2(int[] nums) {
        // 使用min来维护当前位置的前缀和
        int min = 0;
        int ans = Integer.MIN_VALUE;
        int add = 0;
        for(int i = 0 ; i < nums.length ; i ++){
            // add为位置i的前缀和
            add += nums[i];

            ans = Math.max(ans , add - min);
            if(add<min){
                min = add;
            }
        }
        return ans;
    }

    @Test
    public void testmaxSubArray(){
        int[] nums = new int[]{-2,1,-3,4,-1,2,1,-5,4};
        int[] a = new int[]{1};
        int[] b = new int[]{-1};
        System.out.println(maxSubArray(nums));
        System.out.println(maxSubArray(a));
        System.out.println(maxSubArray(b));
    }

}
